﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MaxArea
{
    // original algorithm: http://wansishuang.appspot.com/?p=3002

    class MaxHistogram
    {
        public int FindMax(int[] histo)
        {
            Stack<int> stk = new Stack<int>();
            int leftIndex = -1;
            int maxArea = 0;

            if (histo == null || histo.Length == 0)
                return maxArea;
            else if (histo.Length == 1)
                return histo[0];

            stk.Push(histo[0]);

            for (int i=1; i<histo.Length; i++)
            {
                while (!(stk == null) && stk.Peek() > histo[i])
                {
                    int temp = stk.Pop();
                    int area = (i - leftIndex) * histo[i];
                    if (area > maxArea)
                        maxArea = area;
                }

                if (stk == null)
                    leftIndex = -1;
                else
                    leftIndex = stk.Peek();

                if (stk.Peek() < histo[i])
                {
                    stk.Push(i);
                }
            }

            return maxArea;
        }

        static void Main(string[] args)
        {
        }
    }
}
